#!/usr/bin/env python3

from time import time

def neighborof(node, len_matrix):
  """
return an iterator of neightbors
"""
  filter_outofbound = lambda x: x<len_matrix and x>=0
  neighbor = [(i,node[1]) for i in filter(filter_outofbound,(node[0]-1,node[0]+1))]
  neighbor.extend([(node[0],j) for j in filter(filter_outofbound,(node[1]-1,node[1]+1))])
  return neighbor

def euler83():
  """
  Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.
  """
  matrix = []
  res_list = []
  with open("matrix.txt") as file:
    for line in file.readlines():
      matrix.append(list(map(lambda x: [int(x),float('inf')],line.strip().split(","))))
  check_dist = lambda node: matrix[node[0]][node[1]][1]
  #Let's start Dijkstra's algorithm
  len_matrix = len(matrix)
  matrix[0][0][1] = matrix[0][0][0]
  nodes = [(i,j) for i in range(len_matrix) for j in range(len_matrix)]
  while len(nodes) != 0:
      node = min(nodes, key = check_dist)
      print("node selected : {}".format(node))
      nodes.remove(node)
      for neightbor_node in neighborof(node,len_matrix):
        print("\tneightbor node selected : {}".format(neightbor_node))
        if neightbor_node not in nodes: continue
        print("\tneightbor node validated : {}".format(neightbor_node))
        alt = matrix[node[0]][node[1]][1] + matrix[neightbor_node[0]][neightbor_node[1]][0]
        if alt < matrix[neightbor_node[0]][neightbor_node[1]][1]:
          matrix[neightbor_node[0]][neightbor_node[1]][1] = alt
  return matrix[-1][-1][1]
  

"""
Print answer and process time
"""
if __name__=="__main__":
  time_begin = time()
  print("Answer : {}".format(euler83()))
  print("Time : {}\"".format(time()-time_begin))
